package kyssion.leetcode.num1_50;

public class code44_通配符匹配 {
    public static void main(String[] args) {
        System.out.println(new code44_通配符匹配().isMatch3(
                "aaabbbaaabbb"
                , "*bbb"

        ));
    }

    /**
     * 简单递归算法会超时,因为时间复杂度是阶乘级别的,如有优化需要引入缓存,非常复杂
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s, String p) {
        return ans(s.toCharArray(), p.toCharArray(), 0, 0);
    }

    public boolean ans(char[] s, char[] p, int sindex, int pindex) {
        if (pindex == p.length && sindex == s.length) {
            return true;
        } else if (pindex == p.length && sindex < s.length) {
            return false;
        } else {
            if (sindex == s.length && p[pindex] != '*') {
                return false;
            }
            if (p[pindex] == '*') {
                while (pindex < p.length && p[pindex] == '*') {
                    pindex++;
                }
                for (int a = 0; a + sindex <= s.length; a++) {
                    if (sindex + a < s.length && pindex < p.length && (s[sindex + a] == p[pindex] || p[pindex] == '?')) {
                        if (ans(s, p, sindex + a + 1, pindex + 1)) {
                            return true;
                        }
                    } else if (ans(s, p, sindex + a, pindex)) {
                        return true;
                    }
                }
            } else if (p[pindex] == '?' || p[pindex] == s[sindex]) {
                return ans(s, p, sindex + 1, pindex + 1);
            }
            return false;
        }
    }

    /**
     * 使用动态规划处理
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch2(String s, String p) {
        boolean[] isOks = new boolean[s.length() + 1];
        isOks[0] = true;
        char[] sArr = s.toCharArray();
        char[] pArr = p.toCharArray();
        int pLength = mergeArr(pArr);//合并**这样的请求
        for (int pindex = 0; pindex < pLength; pindex++) {
            char reg = pArr[pindex];
            if (reg != '*') {
                for (int isOkIndex = isOks.length - 1; isOkIndex > 0; isOkIndex--) {
                    if (isOks[isOkIndex - 1] && (reg == sArr[isOkIndex - 1] || reg == '?')) {
                        isOks[isOkIndex - 1] = false;
                        isOks[isOkIndex] = true;
                    } else {
                        isOks[isOkIndex] = false;
                    }
                }
                isOks[0] = false;
            } else {
                if (pindex == 0) {
                    for (int a = 0; a < isOks.length; a++) {
                        isOks[a] = true;
                    }
                } else {
                    int find = isOks.length - 1;
                    int before = find;
                    while (find > 0) {
                        while (find > 0) {
                            if (isOks[find]) {
                                break;
                            }
                            find--;
                        }
                        for (int a = find; a <= before && find > 0; a++) {
                            isOks[a] = true;
                        }
                        find--;
                    }
                }
            }
        }
        return isOks[s.length()];
    }

    public int mergeArr(char[] item) {
        int index = 0;
        for (int a = 1; a < item.length; a++) {
            if (item[a] == '*' && item[a] == item[a - 1]) {
                index++;
            }
            item[a - index] = item[a];
        }
        return item.length - index;
    }


    /**
     * 降维打击  递归写法的训话表达式写法, 心中一万条草泥马跑过
     *
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch3(String s, String p) {
        int i = 0, j = 0, iStar = -1, jStar = -1;
        while (i < s.length()) {
            if (j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                ++i;
                ++j;
            } else if (j < p.length() && p.charAt(j) == '*') {//这里的这个优化点真的值得思考
                                                                //相比较之前第一种递归的写法这里考虑的这种情况的优化,如果*abcd*这个匹配串中 *abcd已经完美匹配了,那么针对之前的那个* 的搜索过程就可以终止了,而是使用后面的这个*
                                                            //因为* 这个通配符提供的后者的搜索过程和前者如果不进行停止的过程是重复的
                iStar = i;
                jStar = j++;
            } else if (iStar >= 0) {
                i = ++iStar;
                j = jStar + 1;
            } else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*')
            ++j;
        return j == p.length();
    }
}
